package org.example.sort;

import java.util.Arrays;

//希尔排序算法思想:基本原理,分组插入排序：希尔排序是插入排序的改进版本，也称"缩小增量排序"
//增量序列：通过设定一个间隔序列（增量序列），将数组按照间隔分成若干子序列
//逐步缩小增量：对每个子序列进行插入排序，然后逐步缩小增量，重复此过程
//最终排序：当增量为1时，对整个数组进行一次插入排序，此时数组基本有序，排序效率较高
//核心特点:非稳定排序：相等元素的相对位置可能会改变,原地排序：只需要常数级别的额外空间
//高效性：比直接插入排序和冒泡排序效率高很多,增量选择：不同的增量序列会影响算法的性能
//工作过程:选择一个增量序列 t1, t2, ..., tk，其中 ti > tj, tk = 1
//按增量序列个数k，对序列进行k趟排序,每趟排序，根据对应的增量ti，将待排序列分割成若干子序列,分别对各子序列进行直接插入排序
//仅当增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度
public class XiErSort {
    public static void main(String[] args) {
        int[] array = {3, 8, 6, 7, 4, 2, 1, 9, 5};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(array));
        shellSort(array);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(array));
    }
    public static void shellSort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 初始增量为数组长度的一半，每次缩小为原来的一半
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 对每个分组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i;
                // 在分组内进行插入排序
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        // 将排序后的结果复制回原数组
        System.arraycopy(arr, 0, sourceArray, 0, sourceArray.length);
    }
    // 另一种实现方式：使用Knuth增量序列
    public static void shellSortKnuth(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 计算初始增量（Knuth序列：1, 4, 13, 40, 121, ...）
        int gap = 1;
        while (gap < arr.length / 3) {
            gap = gap * 3 + 1;
        }
        // 逐步缩小增量
        while (gap >= 1) {
            // 对每个分组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i;
                // 在分组内进行插入排序
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap /= 3;
        }
        // 将排序后的结果复制回原数组
        System.arraycopy(arr, 0, sourceArray, 0, sourceArray.length);
    }
}
